The forward link of 1×EV-DV (see for example “Physical Layer Standard for cdma2000 Spread Spectrum Systems”, IS2000 Release C. 3GPP2 C.S0002-C) uses code division multiplexing (CDM) within time division multiplexing (TDM) (1.25, 2.5 or 5 ms slots) on a shared channel (SHCH) that allows flexible slot scheduling and slots for real time services such as voice and video for multiple users. Each time slot has a set of Walsh codes (WC), and has its power allocation split between one or more voice users. 1×EV-DV allows one data user and multiple voice users per slot. Voice users may take several of the WC codes. For instance, full rate voice users can use either one or two SHCH W16 codes. Half, quarter and eighth rate voice uses convolutional coding and uses only one W16 code.
1×EV-DV allows users to be scheduled over a certain number of slots in every frame (e.g., 20 ms) by allocating Walsh code gains that are to be controlled based on channel estimations from each user. There is no solution for doing this allocation in a manner that maximizes voice capacity.
Voice capacity of 1×EV-DV strongly depends on a scheduling scheme. This implies that an efficient scheduling algorithm is needed in order to maximize the voice capacity. However, scheduling users efficiently over slots in each frame is a very difficult problem because it is a combinatorial optimization problem that is NP-hard (non-polynomial-hard).
Many scheduling algorithms have been proposed in the literature for various purposes. However, there are no scheduling algorithms that can be applied effectively directly to 1×EV-DV. Schemes which have been proposed were to obtain a feasible solution but these do not provide any quality guarantee. For instance, Zig-Zeg or round-robin schemes have been proposed for the forward link due to the difficulty of the NP-hard characteristics of the scheduling problem.